package dichotomy;

import java.util.PriorityQueue;

/**
 * @author Liaorun
 */
public class MinWaitingTime {
    public static int minWaitingTime1(int[] arr, int m) {
        if (arr == null || arr.length == 0) {
            return -1;
        }

        // [0,5]
        // [0,3]
        // 第一位代表当前服务了多少时间，第二位代表每次服务的时间
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
        int n = arr.length;
        // n -> n * logn
        for (int i = 0; i < n; i++) {
            heap.add(new int[]{0, arr[i]});
        }
        // m * logn
        for (int i = 0; i < m; i++) {
            // 弹出最先空闲服务员
            int[] cur = heap.poll();
            // 计算服务了当前用户之后的时间点
            cur[0] += cur[1];
            // 放到小顶堆中排序
            heap.add(cur);
        }
        return heap.peek()[0];
    }


    /**
     * 时间复杂度 n * log(min * m)
     *
     * @param arr cpu处理单个任务的时间，长度为n
     * @param m   任务的数量
     * @return
     */
    public static int minWaitingTime2(int[] arr, int m) {
        if (arr == null || arr.length == 0) {
            return -1;
        }

        // 工作效率最好的服务员
        int best = Integer.MAX_VALUE;
        for (int num : arr) {
            best = Math.min(best, num);
        }
        int left = 0;
        int right = best * m;
        int mid;
        int near = 0;

        while (left <= right) {
            // 尝试只给一半的时间，能服务多少人
            mid = (left + right) / 2;
            int cover = 0;
            for (int num : arr) {
                cover += (mid / num) + 1;
            }
            if (cover >= m + 1) {
                // 我能被服务，是一个不错的时间答案
                near = mid;
                right = mid - 1;
            } else {
                // 我不能被服务，在右侧给更大的时间尝试
                left = mid + 1;
            }
        }

        return near;
    }
}
